{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1a1cd4ed-ef0b-4a28-864c-d3a15c1e7f0f",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/interleaving-string/\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        #9:10\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        if set(s1+s2) != set(s3):\n",
    "            return False\n",
    "        \n",
    "        self.itIsTrue = False\n",
    "        def keepMatchUntilDeath(stringLeft, s1Left, s2Left):\n",
    "            if self.itIsTrue:\n",
    "                return\n",
    "            \n",
    "            #print(f\"stringLeft: {stringLeft}, s1Left: {s1Left}, s2Left: {s2Left}\")\n",
    "            \n",
    "            if len(stringLeft) == 0 and len(s1Left + s2Left) == 0:\n",
    "                self.itIsTrue = True\n",
    "                return \n",
    "            \n",
    "            if len(stringLeft) == 0 and len(s1Left + s2Left) != 0:\n",
    "                return\n",
    "            \n",
    "            for i in range(0,max(len(s1Left), len(s2Left)) + 1):\n",
    "                tempLeft1 = s1Left[:i]\n",
    "                if len(tempLeft1):\n",
    "                    if s1Left[:i] == stringLeft[:i]:\n",
    "                        keepMatchUntilDeath(stringLeft[i:], s1Left[i:], s2Left)\n",
    "                    \n",
    "                tempLeft2 = s2Left[:i]\n",
    "                if len(tempLeft2):\n",
    "                    if s2Left[:i] == stringLeft[:i]:\n",
    "                        keepMatchUntilDeath(stringLeft[i:], s1Left, s2Left[i:])\n",
    "                    \n",
    "        keepMatchUntilDeath(s3, s1, s2)\n",
    "                    \n",
    "        return self.itIsTrue\n",
    "        #9:18\n",
    "        #debug until 9:39, time exceeded, 91/106\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c961e7d6-6228-4d5a-ab42-30046d65b2c9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c24d057-ec07-4cba-a9e2-062f6dd92dc2",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "f443e23a-af7e-41a5-8dba-1979a13b505a",
   "metadata": {},
   "source": [
    "# Start from 2022/12/10 05:57, spent 10 minutes to let the old code pass the check\n",
    "\n",
    "Accepted\n",
    "\n",
    "> Sometimes, timeout means there has no way to go. So return False directly.\n",
    "\n",
    "____\n",
    "\n",
    "Runtime\n",
    "9024 ms\n",
    "\n",
    "Beats\n",
    "5.2%\n",
    "\n",
    "Memory\n",
    "14.2 MB\n",
    "\n",
    "Beats\n",
    "54.31%"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f135156f-8fc9-4490-a6c4-fdea2890e3ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        #9:10\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        if set(s1+s2) != set(s3):\n",
    "            return False\n",
    "        \n",
    "        self.limit = 100000\n",
    "        self.counting = 0\n",
    "        self.itIsTrue = False\n",
    "        def keepMatchUntilDeath(stringLeft, s1Left, s2Left):\n",
    "            if (self.counting > self.limit):\n",
    "                return\n",
    "            self.counting += 1\n",
    "\n",
    "            if self.itIsTrue:\n",
    "                return\n",
    "            \n",
    "            #print(f\"stringLeft: {stringLeft}, s1Left: {s1Left}, s2Left: {s2Left}\")\n",
    "            \n",
    "            if len(stringLeft) == 0 and len(s1Left + s2Left) == 0:\n",
    "                self.itIsTrue = True\n",
    "                return \n",
    "            \n",
    "            if len(stringLeft) == 0 and len(s1Left + s2Left) != 0:\n",
    "                return\n",
    "            \n",
    "            for i in range(0,max(len(s1Left), len(s2Left)) + 1):\n",
    "                tempLeft1 = s1Left[:i]\n",
    "                if len(tempLeft1):\n",
    "                    if tempLeft1 == stringLeft[:i]:\n",
    "                        keepMatchUntilDeath(stringLeft[i:], s1Left[i:], s2Left)\n",
    "                    \n",
    "                tempLeft2 = s2Left[:i]\n",
    "                if len(tempLeft2):\n",
    "                    if tempLeft2 == stringLeft[:i]:\n",
    "                        keepMatchUntilDeath(stringLeft[i:], s1Left, s2Left[i:])\n",
    "                    \n",
    "        keepMatchUntilDeath(s3, s1, s2)\n",
    "                    \n",
    "        return self.itIsTrue\n",
    "        #9:18\n",
    "        #debug until 9:39, time exceeded, 91/106\n",
    "\n",
    "        #start from 2022/12/10 05:57, spent 10 minutes to let the old code pass the check"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62be3c6f-f69d-4cee-bb38-a96036a8947d",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}